#define _CRT_SECURE_NO_WARNINGS 1

//int missingNumber(int* nums, int numsSize)
//{
//	int x = 0;
//	int n = numsSize;
//	//[0,n]
//	for (int i = 0; i <= n; ++i)
//	{
//		x ^= i;
//	}
//
//	for (int j = 0; j < numsSize; ++j)
//	{
//		x ^= nums[j];
//	}
//
//	return x;
//}



////[left, right]
//void Reverse(int* a, int left, int right)
//{
//	while (left < right)
//	{
//		int tmp = a[left];
//		a[left] = a[right];
//		a[right] = tmp;
//
//		++left;
//		--right;
//	}
//}
//
//void rotate(int* nums, int numsSize, int k)
//{
//	k %= numsSize;
//
//	//[0, numsSize-k-1]
//	Reverse(nums, 0, numsSize - k - 1);
//	//[numsSize-k, numsSize-1]
//	Reverse(nums, numsSize - k, numsSize - 1);
//	//[0, numsSize-1]
//	Reverse(nums, 0, numsSize - 1);
//}



//#include <string.h>
//
//void rotate(int* nums, int numsSize, int k)
//{
//	k %= numsSize;
//
//	int tmp[numsSize];
//	int n = numsSize;
//
//	memcpy(tmp, nums + n - k, sizeof(int) * k);
//	memcpy(tmp + k, nums, sizeof(int) * (n - k));
//	memcpy(nums, tmp, sizeof(int) * n);
//}



#include <stdio.h>
#include <stdbool.h>

typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;

struct ListNode* middleNode(struct ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;

	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	return slow;
}

struct ListNode* reverseList(struct ListNode* head)
{
	if (NULL == head)
	{
		return head;
	}

	ListNode* n1, * n2, * n3;
	n1 = NULL, n2 = head, n3 = head->next;

	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;

		if (n3)
		{
			n3 = n3->next;
		}
	}

	return n1;
}

bool chkPalindrome(ListNode* A)
{
	ListNode* mid = middleNode(A);
	ListNode* rmid = reverseList(mid);

	while (A && rmid)
	{
		if (A->val != rmid->val)
		{
			return false;
		}

		A = A->next;
		rmid = rmid->next;
	}

	return true;
}